Tháp tùng Romanos là Andronikos Doukas, con trai của kình địch Ioannes Doukas. Quân đội bao gồm khoảng 5.000 binh lính Đông La Mã chuyên nghiệp từ các tỉnh phía tây và có thể là cũng là chừng đó người các tỉnh phía đông; 500 lính đánh thuê Frank và Norman dưới quyền chỉ huy của Roussel de Bailleul; ngoài ra còn một số lính đánh thuê người Đột Quyết (bao gồm người Ô Cổ Tư và người Pecheneg) và Bulgari; bộ binh dưới quyền chỉ huy của công tước xứ Antiochia; một đội quân từ Gruzia và Armenia; và một số (nhưng không phải tất cả) binh lính của đội cận vệ Varangoi. Quân đội đông chinh của Đông La Mã có tổng cộng khoảng 40.000 đến 70.000 người.[16][17] Số lượng quân đội từ các tỉnh đã bị giảm trong những năm trước khi Romanos lên ngôi, khi triều đình chuyển sang sử dụng lính đánh thuê được đánh giá là ít có khả năng can thiệp vào chính trị hơn và có thể giải tán bất cứ khi nào sau khi sử dụng để tiết kiệm tiền bạc.

Cuộc hành quân xuyên Tiểu Á diễn ra lâu và khó khăn. Romanos còn khiến binh lính bức xúc khi cho áp tải hành lí sang trọng đi cùng; người dân địa phương cũng bị những người lính đánh thuê người Frank quấy nhiễu, cướp bóc, khiến ông phải sa thải họ. Quân viễn chinh nghỉ ngơi tại Sebasteia trên sông Halys và đến Theodosiopolis vào tháng 6 năm 1071. Tại đây, một số tướng của ông đưa ra sách lược đánh vào lãnh thổ Seljuk và đánh phủ đầu Alp Arslan trước khi ông ta sẵn sàng. Trong khi các tướng khác, bao gồm Nikephoros Bryennios, lại khuyên họ nên chờ đợi và củng cố vị trí. Cuối cùng, Romanos đã quyết định tiến binh.

Nghĩ rằng Alp Arslan đang còn ở xa, Romanos tiến về phía hồ Van, dự kiến sẽ nhanh chóng chiếm lại Manzikert, cũng như pháo đài Khliat gần đó nếu có thể. Tuy nhiên, Alp Arslan đã ở trong khu vực cùng với đồng minh và 30.000 kỵ binh từ Aleppo và Mosul. Trinh thám của Alp Arslan đã biết chính xác vị trí của Romanos, trong khi Romanos lại hoàn toàn không ý thức được những chuyển động của đối phương.

Romanos ra lệnh cho tướng Ioseph Tarchaniotes đem một số quân chính quy và cận vệ Varangoi đi cùng với người Pecheneg và Frank tới Khliat, trong khi Romanos và phần còn lại của quân đội tiến thẳng tới Manzikert. Điều này đã khiến quân đội Đông La Mã bị phân chia một nửa, mỗi bên khoảng 20.000 lính. Không rõ chuyện gì đã xảy ra với đội quân đi theo Tarchaniotes - theo các tài liệu Hồi giáo, Alp Arslan đã đánh tan quân đội này, nhưng tài liệu La Mã không đề cập đến bất kỳ cuộc chạm trán nào như vậy. Trong khi đó, sử gia Attaliates đã cho rằng Tarchaniotes đã đầu hàng Sultan người Thổ - một điều khó xảy ra nếu xem xét thanh danh của tướng sĩ La Mã. Dù bằng cách nào đi chăng nữa, quân đội của Romanos đã giảm xuống còn chưa tới một nửa số lượng 40.000 đến 70.000 người theo kế hoạch.[16][18]